|
The Wolfram axiom is the result of a computer exploration undertaken by Stephen Wolfram〔Stephen Wolfram, A New Kind of Science, 2002, p. 808–811 and 1174.〕 in his A New Kind of Science looking for the shortest single axiom equivalent to the axioms of Boolean algebra (or propositional calculus). The result〔Rudy Rucker, A review of NKS, The Mathematical Association of America, Monthly 110, 2003.〕 of his search was an axiom with six Nand's and three variables equivalent to Boolean algebra: : With the dot representing the Nand logical operation (also known as the Sheffer stroke), with the following meaning: ''p'' Nand ''q'' is true if and only if not both ''p'' and ''q'' are true. It is named for Henry M. Sheffer, who proved that all the usual operators of Boolean algebra (Not, And, Or, Implies) could be expressed in terms of Nand. This means that logic can be set up using a single operator. Wolfram’s 25 candidates are precisely the set of Sheffer identities of length less or equal to 15 elements (excluding mirror images) that have no noncommutative models of size less or equal to 4 (variables).〔William Mccune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist and Larry Wos, Short Single Axioms for Boolean algebra, J. Automated Reasoning, 2002.〕 Researchers have known for some time that single equational axioms (i.e., 1-bases) exist for Boolean algebra, including representation in terms of disjunction and negation and in terms of the Sheffer stroke. Wolfram proved that there were no smaller 1-bases candidates than the axiom he found using the techniques described in his NKS book. The proof is given in two pages (in 4-point type) in Wolfram's book. Wolfram's axiom is therefore the single simplest axiom by number of operators and variables needed to reproduce Boolean algebra. Sheffer identities were independently obtained by different means and reported in a technical memorandum〔Robert Veroff and William McCune, A Short Sheffer Axiom for Boolean algebra, Technical Memorandum No. 244〕 in June 2000 acknowledging correspondence with Wolfram in February 2000 in which Wolfram discloses to have found the axiom in 1999 while preparing his book. In〔Robert Veroff, Short 2-Bases for Boolean algebra in Terms of the Sheffer stroke. Tech. Report TR-CS-2000-25, Computer Science Department, University of New Mexico, Albuquerque, NM〕 is also shown that a pair of equations (conjectured by Stephen Wolfram) are equivalent to Boolean algebra. ==See also== *Boolean algebra 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Wolfram axiom」の詳細全文を読む スポンサード リンク
|